The present invention relates to an apparatus and method for processing a Viterbi algorithm, which may be used, for example, in a digital mobile communications system.
Viterbi decoders are used in digital wireless communication receivers to correct bit errors that occur in the wireless communication channel. With the Viterbi technique, an original data stream is encoded prior to transmission by adding bits thereto in a predetermined manner. The encoded bit stream is transmitted in a noisy channel which may produce bit errors due to multipath fading and the like. On the receive side, by decoding the received data stream using the Viterbi algorithm, the original data stream can be reproduced despite the occurrence of bit errors in the channel, provided that the number of bit errors is not excessive. Viterbi decoders operate by implementing a sequence determining method modeling a Gaussian channel.
Viterbi algorithms are widely used in mobile communications receivers owing to their excellent error correction rates. However, the Viterbi algorithm approach does involve substantial calculations and implementation time. In particular, the add-compare select (ACS) and trace-back portions of the computation require the most processing time. The ACS portion is used to determine the number of states in a convolutional encoder when a constraint length xe2x80x9cKxe2x80x9d is applied to the encoder. The trace-back portion uses simulation to determine a path length which plays an important role in determining the performance of the Viterbi algorithm.
In various mobile communication terminals which use time division multiple access (TDMA), such as in the Global Systems Mobile (GSM) system (a European digital mobile communications standard), since the time for processing received data is predetermined, the Viterbi algorithm must be as fast as possible. For example, since a TDMA cycle of the GSM system is limited to 4.615 ms, it is important to have a time margin for the purpose of achieving stable operation.
Recently, baseband systems have been implemented with digital signal processing (DSP). Since the Viterbi algorithm processing portion of the DSP requires numerous calculations and fast processing speed, a separate co-processing system is necessary. Although the Viterbi algorithm is determined in advance, there is still the possibility of improvements in design which increase speed and efficiency.
FIG. 1 is a block diagram of a conventional Viterbi decoder. A branch metric calculator (BMC) 1b receives a digital signal and calculates a branch metric value as probabilistic information. An add-compare selector (ACS) 2b uses the branch metric value from the BMC 1b to update a previous path metric corresponding to each state in a trellis. The ACS 2b compares the updated path metrics with each other and outputs a selected path metric and a determining bit. In a metric memory 3b, the path metric selected by the ACS 2b is fed back to the ACS 2b in a subsequent step. A path memory 4b stores the determining bit output from the ACS 2b. A trace-back controller 5b implements a trace-back operation using the determining bit stored in the path memory 4b and traces back the sequence of original information.
The conventional design of the ACS 2b will now be described. For the sake of explanation, an example of four states will be used. It is necessary to trace the most likely metric in the Viterbi algorithm for searching proper data. The following formula is used for calculating a survival metric in the Viterbi algorithm:
Mn,s0=max(Mnxe2x88x921p0+bmc1p0s0,Mnxe2x88x921p1+bmc2p1s0)
Mn,s1=max(Mnxe2x88x921p2+bmc1p2s1,Mnxe2x88x921p3+bmc2p3s1)
Mn,s2=max(Mnxe2x88x921p0+bmc1p0s2,Mnxe2x88x921p1+bmc2p1s2)
Mn,s3=max(Mnxe2x88x921p2+bmc1p2s3,Mnxe2x88x921p3+bmc2p3s3)xe2x80x83xe2x80x83(1)
where M implies the survival metric of two metric values.
The BMC 1b generates the same metric value as that of the convolutional encoder and obtains the difference from received data, to generate branch metrics such as bmc1p0s0 and bmc2p1s0. Thus, the survival metric of the present state is the larger value of two values, i.e., the first value being the sum of a first previous metric value and a first branch metric (of the present state) and the second value being the sum of a second previous metric value and a second branch metric (of the next state). To this end, at least two adders and a comparator are necessary.
To calculate the survival metric of the present state, the previous metric value stored in the metric memory 3b is read and compared with a value obtained by adding the read metric value and the present metric value. Then the most similar value to the transmitted value is searched.
FIG. 2 illustrates metric values of the respective states and calculated branch metric values for calculating the survival metric of the Viterbi algorithm. As shown, to calculate the metric value of a state 00, the previous metric value Mnxe2x88x921p0 is read. Then, a value obtained by adding the same to bmc1p0s0 is compared with a value obtained by adding Mnxe2x88x921p1 to bmc2p1s0. Of the two values, the larger value is determined as the survival metric (Mn,s0) of the state 00. Thus, to obtain one survival metric value, two cycles are required in each state just for reading the previous metric values. In other words, to calculate the survival metric value, the previous metric values 0 and 1 must be read in the state 00, and the previous metric values 2 and 3 must be read in the state 01. To calculate the survival metric values in the case of four states (e.g., states 00, 01, 10 and 10 in FIG. 2), eight cycles are required just for reading the previous metric values.
Thus, with the above approach, the metric memory must be frequently accessed, resulting in excessive operations and power consumption. Also, since many clock cycles are required to compute survival metrics, this method is not suitable for a high speed Viterbi algorithm implementation, such as in a GSM communication system.
A Viterbi algorithm processing apparatus as that discussed above is useful for both a Viterbi equalizer and a Viterbi decoder. The term xe2x80x9cequalizerxe2x80x9d is a generic term for a signal processing device that can demodulate or decode a signal while compensating for certain imperfections in the radio link. The Viterbi equalizer effectuates this by using a model of the channel or propagation paths which is applied to hypothesized symbol sequences to predict what should be received. The hypothesis that most closely matches the actual received signal is then retained.
FIG. 3A is a block diagram of a Viterbi algorithm processing apparatus 25 included in a Viterbi equalizer. The structure is similar to the decoder of FIG. 1, except the BMC 1b is replaced by a Euclidean Distance Calculator (EDC) 1a. FIG. 3B is a block diagram of a Viterbi equalizer including the Viterbi algorithm processing apparatus.
Referring to FIG. 3B, an impulse response estimator 20 receives input data and measures a channel impulse response of the received data. A filter 10 is implemented by a finite impulse response (FIR) filter designed to have the maximum signal-to-noise ratio at the output terminal at a particular time. The filter 10 is a matched filter which multiplies a reversal of the channel impulse response input from the impulse response estimator 20 by the received data and then time-shifts the multiplied value. Viterbi algorithm processing apparatus 25 receives the data output from the filter 10 and the channel impulse response from the impulse response estimator 10 and performs the Viterbi algorithm for equalization. A demodulator 40 MSK demodulates data output from the Viterbi algorithm processing apparatus 25. A reliability calculator 50 calculates the reliability of the data processed in the Viterbi algorithm processing apparatus 25.
Such a Viterbi equalizer can be implemented by a digital signal processor (DSP) or by hardware (e.g., an equalizer processor or a VLSI). However, when realized by a DSP, the Euclidean distance calculations of the Viterbi algorithm are more complicated, and there are more bit operations at the ACS and trace-back portions, resulting in a complex processing task which increase the power consumption. In addition, to satisfy the system timing, some DSP makers provide coprocessors. When realized by hardware, multipliers, dividers and adders are required according to the characteristics of the filter or the Viterbi algorithm, raising a complexity problem. Also, if the Viterbi equalizer is implemented by an ASIC (Application Specific Integrated Circuit) a chip size problem may arise.
An object of the present invention is to provide an apparatus and method for processing a Viterbi algorithm, which increases the processing speed of the computationally complex ACS portion, thereby reducing power consumption.
Another object of the present invention is to provide a small high-speed Viterbi algorithm processing apparatus by divisionally designing the Viterbi algorithm into a portion to be processed by a digital signal processor and another portion to be processed by hardware according to the contents of the algorithm so as to increase the efficiency.
In one aspect of the invention, a high-speed add-compare selection circuit for a Viterbi algorithm processing apparatus having a branch metric calculator and a metric memory includes: first and second registers for temporarily storing first and second previous metric values read from the memory; a first adder for adding the first previous metric value from the first register and a branch metric value of the present state calculated by the branch metric calculator; a second adder for adding the second previous metric value from the second register and a branch metric value of the next state calculated by the branch metric calculator; and a comparator for comparing the outputs of the first and second adders and calculating a survival metric value accordingly.
The high-speed add-compare selection circuit may also be used as part of a Viterbi equalizer having a Euclidian value calculator. In this case, the first and second adders add metric values from the registers with Euclidian values from the Euclidian value calculator in place of the branch metric values from the branch metric calculator.
Advantageously, the add-compare selection circuit allows for faster Viterbi processing time as compared to the conventional art. The improvement in processing time stems from the reduction in the number of metric memory accesses required to read metric value data, and the attendant reduction in the number of clock cycles needed to compute survival metrics.